package cn.orange.ch07_binarytree;

import cn.orange.TreeNode;

/**
 * LC110.平衡二叉树
 给定一个二叉树，判断它是否是平衡二叉树
 */
public class LC110 {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    private int getHeight(TreeNode root) {
        if (root == null) return 0;
        int heightL = getHeight(root.left);
        if (heightL == -1) return -1;
        int heightR = getHeight(root.right);
        if (heightR == -1) return -1;
        if (Math.abs(heightL - heightR) > 1) {
            return -1;
        } else {
            return 1 + Math.max(heightL, heightR);
        }
    }

    public static void main(String[] args) {
        LC110 alg = new LC110();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.right = new TreeNode(15);
        root.right.left = new TreeNode(7);
        System.out.println(alg.isBalanced(root));
    }
}
